package P215;

import org.junit.Test;

/**
 * @Author DJ同学
 * @Date 2021/3/2 18:18
 * @Version 1.0
 *
 */
public class Knowledge {
/*
    堆其实就是优先队列
    使用完全二叉树来实现堆
    可以用数组来实现,但是注意存放从下标为1的地方开始
    下面以最大堆为例子
 */

    Integer[] maxHeap;
    int size = 0;//当前容量
    @Test
    public void test(){
        Integer[] nums = new Integer[]{1,2,3,6,8};

        maxHeap = new Integer[nums.length+1];//+1需要注意哦
        maxHeap[0] =Integer.MAX_VALUE;//设置哨兵

        //插入节点 放到尾巴，然后和父节点比较，一直到哨兵结束
        for(Integer num:nums){
            add(num);
        }
        for (int i = 0; i < maxHeap.length; i++) {
            System.out.println(maxHeap[i]);
        }
        //删除节点 将最后一个节点放到头节点，然后去调整位置
        System.out.println("-------------------------------");
        while(size>0){
            Integer delete = delete();
            System.out.println(delete);
        }

    }

    void add(Integer num){
        //将节点放到尾巴
        maxHeap[++size]=num;
        int j = size;
        //向上比较
        for(;num>maxHeap[j/2];j=j/2){
            maxHeap[j]=maxHeap[j/2];
        }
        //最后放入值
        maxHeap[j] = num;
    }
    //删除堆顶
    Integer delete()  {
        if(size==0){
            return -1;//"堆中没有元素了";
        }
        int res = maxHeap[1];
        int temp = maxHeap[size--];//temp一直是和child做比较
        //调整结构
        int parent = 1;
        int child = 2*parent;
        while (child<=size){

            //左右子节点比较
            if(child+1<=size&&maxHeap[child]<maxHeap[child+1]){
                child++;
            }
            if(temp<maxHeap[child]){
                maxHeap[parent]=maxHeap[child];
                parent = child;
                child = 2*parent;
                continue;
            }else{
                break;
            }
        }
        maxHeap[parent] = temp;
        return res;

    }
}
